Aliasing is an important problem when rendering triangle or other polygonal meshes. Computer graphics has long dealt with the issue of creating discrete images without aliasing. For the hardware-accelerated triangle rendering pipeline, four forms of aliasing can be identified:                (1) Aliasing within triangle interiors (undersampling of shading function). One such example is aliasing due to texture undersampling, which can be efficiently handled using mipmaps or higher-quality anisotropic filtering. Other shading variations, like pinpoint specular highlights, can exhibit high frequencies that are more difficult to predict and bandlimit.        (2) Aliasing at triangle edges (appearance discontinuities).        (3) Aliasing among triangles (subpixel-sized triangles, also known as the “small object” problem). This problem is partially helped by level-of-detail control. Robust solution requires adequate supersampling or analytic anti-aliasing.        (4) Aliasing at triangle intersections (where one triangle passes through another). Static intersections can be preprocessed to yield explicit sharp edges using polyhedral CSG. Dynamic intersections are difficult to anti-alias without supersampling.        
With current graphics hardware, a simple technique for reducing aliasing is to supersample and filter the output image. On current displays (desktop screens of approximately 1K×1K resolution), 2×2 supersampling reduces but does not eliminate aliasing. Of course, a finer supersampling resolution further reduces aliasing but rapidly becomes impractical.
One can implement 2×2 supersampling either by increasing the frame buffer resolution by a factor of four, or by accumulating four subpixel-offset images of the same scene for each frame. Both approaches are costly. The first requires four times the frame buffer memory and four times the fill-rate. The second requires four times the geometry processing, four times the fill-rate, and the addition of an accumulation buffer. The impact is that fill-rate-bound rendering becomes up to four times slower, and memory capacity is consumed that could otherwise be devoted to storing texture maps or caching geometry.
Much of the aliasing in current hardware rendering occurs along discontinuity edges. Perhaps most objectionable are the “crawling jaggies” that appear near discontinuity edges as a model moves. FIG. 1 shows a magnified triangle edge 100 to illustrate such “crawling jaggies”. The edge 100 is drawn on a grid 102 of pixels 104. Pixels touching the edge 100 are assigned to the triangle edge, resulting in a stair-stepped, jagged artifact 106. When the image moves, this jagged artifact appears to crawl along the edge, making them highly noticeable to an observer.
Such artifacts are perceptible even at high display resolutions where static spatial aliasing is less obvious, and are observable even with 2×2 supersampling. Since discontinuity edges typically cover only a small fraction of pixels, supersampling every pixel seems a brute-force solution.
Many general techniques to reduce aliasing have been used in computer graphics, including uniform supersampling, adaptive supersampling, analytic prefiltering, and stochastic sampling. Adaptive supersampling attempts to focus computation on troublesome areas such as discontinuity edges. However, adaptive supersampling is difficult to make robust and implement in hardware. Prefiltering approaches band-limit the continuous signal corresponding to a geometric primitive (such as a constant-colored polygon fragment), before actually point-sampling it. They require expensive visibility determinations over areas rather than points. Stochastic sampling methods convert aliasing to less objectionable noise (rather than “crawling jaggies”), but still require oversampling to acceptably reduce aliasing artifacts.
Coverage bitmask approaches supersample only coverage rather than full r, g, b, z samples. These are effective at reducing artifacts at discontinuity edges, but fail to eliminate aliasing at triangle intersections. Like traditional uniform supersampling, they are brute-force solutions since a coverage bitmask must be computed and stored at every pixel (typically 16-32 extra bits). Moreover, these schemes maintain a list of fragments projecting onto each pixel.
The OpenGL® application program interface (API) introduced by SGI offers a “polygon anti-aliasing” feature, available on some high-end graphics workstations, that renders polygons with anti-aliased boundaries. It uses a special blending mode (source_alpha_saturate) and only works when the polygons are sorted front-to-back. A similar feature is also exposed in the DirectX® API from Microsoft Corporation.
Another approach is to only anti-alias discontinuity edges. One technique is to tag discontinuity edges and anti-alias them using prefiltering convolution in a scanline renderer. Another technique infers discontinuity edges in an aliased image as a post-process. Pixels near discontinuities are then modified to account for coverage of the inferred edges. This method gets confused at texture discontinuities, ignores temporal aliasing, and is likely too expensive to perform at interactive rates.
More recently, silhouette clipping has been proposed as a way to reduce anti-aliasing along discontinuity edges. See, P. Sander, X. Gu, S. Gortler, H. Hoppe, and J. Snyder, “Silhouette Clipping”, SIGGRAPH 2000, pp. 327-334. With silhouette clipping, a coarse mesh is clipped to the exact silhouette of a detailed mesh using the stencil buffer. By transferring the stencil to the alpha buffer and redrawing silhouette edges as anti-aliased lines, the external silhouette is anti-aliased. However, this solution is limited to external silhouettes, and is not more generally applied to reducing aliasing at both internal and external silhouettes, as well as all discontinuity edges.
In another recent paper, the authors sketch a two-pass software rendering approach for anti-aliasing silhouette edges. See, F. Sauer, O. Masclef, Y. Robert, and P. Deltour, “Outcast: programming towards a design aesthetic”, 1999 Game Developers Conference, pp. 811-827. Unfortunately, the second pass bloats foreground pixels near silhouettes by computing edge coverage at each pixel. The method handles only silhouettes and detects these by exhaustive search. The paper lacks details on how polygons are rasterized or how the two passes are composited. U.S. Pat. No. 6,005,580 to Donovan, which is entitled “Method and Apparatus for Performing Post-Process Anti-aliasing of Polygon Edges”, describes a hardware approach that transfers the aliased frame buffer contents into texture memory, and uses this texture to overdraw anti-aliased edges in a second pass.
Another solution proposed by M. Wimmer in his downloadable viewer “View3DX software” is to overdraw anti-aliased lines. Unfortunately, this approach failed without software sorting of all polygons.
The documentation for Microsoft's DirectX® software also mentions the use of edge overdraw to achieve anti-aliasing. It explains that redrawing every edge in a scene can work without introducing major artifacts, but it can also be computationally expensive. In addition, it can be difficult to determine which edges should be anti-aliased. The most important edges to redraw are those between areas of very different color (for example, silhouette edges) or boundaries between very different materials. Anti-aliasing the edge between two polygons of roughly the same color will have no effect, yet is still computationally expensive.
Building upon this knowledge base, the inventors have developed an edge overdraw approach that effectively reduces aliasing. They make the approach practical by efficiently detecting and rendering just the discontinuity edges, and introduce methods to maintain temporal smoothness, spatial consistency, and spatial sharpness.